#include<stdio.h>

void Swap(int *a,int *b)
{
    int c = *b;
    *b = *a;
    *a = c;
}


//冒泡排序
void BubbleSort(int *a,int size)
{
    for(int i = 0; i < size -1; i++) //外循环代表次数
    {
        int flag = 0;
        for(int j = 0;j< size - i - 1;j++)
        {
            flag = 1;
            if(a[j] > a[j+1])    
            {
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag == 0)   //数列已经有序
            break;
    }
}


//插入排序
void InsertSort(int *a,int size)
{
    for(int i = 1;i < size;i++)  //要插入的数的下标
    {
        int j = i;   //当前要插入的数的下标
        int temp = a[i];   //要插入的值
        for(;j>0;j--)   
        {
            if(a[j-1]>temp)   //前面这个数比我大
                a[j] = a[j-1];
            else             //前面这个数比我小
                break;    
        }
        a[j] = temp;
    }
}

//选择排序
//找到后面的数列中最小的值和自己换
void ChooseSort(int *a,int size)
{
    for(int i = 0; i < size - 1; i++)
    {
        int min = i;
        for(int j = i + 1; j < size; j++)
        {
            if(a[min] > a[j])
                min = j;
        }
        Swap(&a[i],&a[min]);
    }
}
//双指针版本的选择排序
void ChooseSortDouble(int *a,int size)
{
    int left = 0;            //左指针
    int right = size - 1;    //右指针
    while(left < right)
    {
        int min = left,max = right;
        for(int i = left; i <= right; i++)
        {
            if(a[min] > a[i])
                min = i;
            if(a[i] > a[max])
                max = i;
        }
        Swap(&a[left],&a[min]);
        //极值在两端，可能会换两次
        if(max == left)
        {
            max = min;
        }
        Swap(&a[right],&a[max]);
        left++;
        right--;
    }
}



//快速排序 : 双指针 + 递归
void FastSort(int *a,int start,int end)
{
    if(start >= end)  //终止条件
        return;
     int left = start;
     int right = end;
     int temp = a[left]; //将最左边的值定为基准值
     while(left < right)
     {
        //右边往左动，找比基准值小的数
        while (a[right]>temp && left < right) 
            right--;
        if(left < right)
            a[left++] = a[right]; //把右边比基准值小的数扔到左边
        
        //左边往右动，找比基准值大的数
        while (a[left]<temp && left < right) 
            left++;
        if(left < right)
            a[right--] = a[left]; //把左边比基准值大的数扔到右边
     }
     a[left] = temp;
     FastSort(a,start,left-1);
     FastSort(a,right+1,end);
}

int BinarySearch(int *a,int size,int element)
{
    int left = 0;
    int right = size - 1;
    while(left <= right)
    {
        // int mid = left + (right - left) / 2; // 防止溢出
        int mid = (left & right) + ((left ^ right) >> 1);
        if(a[mid] > element)
            right = mid - 1;
        else if(a[mid] < element)
            left = mid + 1;
        else 
            return mid;
    }
    return -1;
}

void PrintArray(int *a,int size)
{
    for(int i=0;i<size;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}

int main()
{
    int a[10] = {4,3,1,2,5,65,34,56,23,65};
    FastSort(a,0,9);
    //PrintArray(a,10);
    //printf("%d\n",BinarySearch(a,10,56));
    return 0;
}

